package com.github.yangyishe.p100;

/**
 * 63. 不同路径 II
 * https://leetcode.cn/problems/unique-paths-ii/description/?envType=study-plan-v2&envId=top-interview-150
 *
 * 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
 *
 * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
 *
 * 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
 *
 * 网格中的障碍物和空位置分别用 1 和 0 来表示。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
 * 输出：2
 * 解释：3x3 网格的正中间有一个障碍物。
 * 从左上角到右下角一共有 2 条不同的路径：
 * 1. 向右 -> 向右 -> 向下 -> 向下
 * 2. 向下 -> 向下 -> 向右 -> 向右
 * 示例 2：
 *
 *
 * 输入：obstacleGrid = [[0,1],[0,0]]
 * 输出：1
 *
 *
 * 提示：
 *
 * m == obstacleGrid.length
 * n == obstacleGrid[i].length
 * 1 <= m, n <= 100
 * obstacleGrid[i][j] 为 0 或 1
 */
public class Problem63 {
    public static void main(String[] args) {
        int[][] obstacleGrid=new int[][]{
                {0,0,0},
                {0,1,0},
                {0,0,0},
        };

        Problem63 problem63 = new Problem63();
        int paths = problem63.uniquePathsWithObstacles(obstacleGrid);
        System.out.println("paths = " + paths);

    }

    /**
     * 思路:
     * 由于机器人只能向右或下走, 所以高级情况可以参考低级情况而不会影响低级情况, 可以使用动态规划
     *
     * 创建一个与网格大小相同的二维数组, 记录在考虑障碍物的情况下路径的数量
     * 1. 第一行和第一列, 均为1(在不考虑障碍物的情况);
     * 2. 障碍物为0; (优先级最高!!!)
     * 3. 其他情况, 则等于左侧单元格与上侧单元格的路径数量之和.
     *
     *
     *
     * @param obstacleGrid
     * @return
     */
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        //1. 创建路径和二维数组
        int height = obstacleGrid.length;
        int width = obstacleGrid[0].length;
        int[][] routes=new int[height][width];

        //2. 初始化
        if(obstacleGrid[0][0]==1){
            return 0;
        }
        routes[0][0]=1;
        boolean obs=false;
        for(int c=1;c<width;c++){
            if(obstacleGrid[0][c]==1){
                obs=true;
            }
            routes[0][c]=obs?0:1;
        }
        obs=false;
        for(int r=1;r<height;r++){
            if(obstacleGrid[r][0]==1){
                obs=true;
            }
            routes[r][0]=obs?0:1;
        }

        //3. 遍历推进
        for(int r=1;r<height;r++){
            for(int c=1;c<width;c++){
                if(obstacleGrid[r][c]==1){
                    routes[r][c]=0;
                }else{
                    routes[r][c]=routes[r-1][c]+routes[r][c-1];
                }
            }
        }

        //4. 返回值

        return routes[height-1][width-1];
    }
}
